//最小栈
//https://leetcode.cn/problems/min-stack/
class MinStack {
public:
    MinStack() {}
    
    void push(int val) 
    {
        st.push(val);
        if(minst.empty() || minst.top() >= val)
        {
            minst.push(val);
        }
    }
    
    void pop() 
    {
        if(st.top() == minst.top())
        {
            minst.pop();
        }
        st.pop();
    }
    
    int top() 
    {
        return st.top();
    }
    
    int getMin() 
    {
        return minst.top();
    }

    stack<int> st;
    stack<int> minst;
};

//详细见笔记练习题
//栈的压入、弹出序列
//https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
#include <iterator>
class Solution {
public:
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) 
    {
        // write code here
        /*stack<int> st;
        size_t j = 0;
        for(size_t i = 0; i < pushV.size(); ++i)
        {
            st.push(pushV[i]);
            for(; j <= i; ++j)
            {
                if(st.top() == popV[j])
                    st.pop();
                else
                    break;
            }
            
        }
        if(!st.empty())
            return false;
        else
            return true;*/
        stack<int> st;
        size_t i = 0, j = 0;
        while(i < pushV.size())
        {
            st.push(pushV[i]);
            ++i;
            while(!st.empty() && (st.top() == popV[j]))
            {
                st.pop();
                ++j;
            }
        }
        return st.empty();
    }
};

//逆波兰表达式求值
//https://leetcode.cn/problems/evaluate-reverse-polish-notation/
class Solution {
public:
    int evalRPN(vector<string>& tokens) 
    {
        stack<int> st;
        for(auto& str : tokens)
        {
            if(str == "+" || str == "-" || str == "*" || str == "/")
            {
                int right = st.top();
                st.pop();
                int left = st.top();
                st.pop();

                switch(str[0])
                {
                    case '+':
                        st.push(left+right);
                        break;
                    case '-':
                        st.push(left-right);
                        break;
                    case '*':
                        st.push(left*right);
                        break;
                    case '/':
                        st.push(left/right);
                        break;
                }
            }
            else
            {
                st.push(stoi(str));
            }
        }
        return st.top();
    }
};